.. _Ассоциативные массивы:

Ассоциативные массивы
======================

.. index::
    aссоциативные массивы

Ассоциативные массивы - это функциональость, которая присутствует в большинстве современных
языков высокого уровня. Это очень быстрые структуры данных, которые работают как мини-базы данных и
используются во многих программах. Мы видели в главе "Массивы" (стр. 49), что простые массивы -
это контейнеры, которые хранят свои элементы один за оодним  и предоставляют доступ к ним по индексу.
Массив, хранящий названия дней недели, может быть определен следующим образом:

.. code-block:: d

    string[] dayNames = [ "Monday", "Tuesday", "Wednesday", "Thursday",
                          "Friday", "Saturday", "Sunday" ];

Название дня может быть получено по его индкесу в этом массиве

.. code-block:: d

    writeln(dayNames[1]); // напечатает "Tuesday"


Тот факт, что простые массивы предоставляют доступ к своим значениям через номера индексов
, можно описать как ассоциацию индексов со значениями. Другими словами, массивы
сопоставляют индексы значениям. Простые массивы могут использовать в качестве индексов только целые числа.
Ассоциативные массивы позволяют индексировать не только с использованием целых чисел, но и с использованием любого
другого типа. Они сопоставляют значения одного типа со значениями другого типа.
Значения типа, из которого сопоставляются ассоциативные массивы, называются ключами, а не
индексами. Ассоциативные массивы хранят свои элементы в виде пар ключ-значение.
Ассоциативные массивы реализованы в D с использованием хэш-таблицы. Хэш-таблицы являются
одними из самых быстрых коллекций для хранения элементов и доступа к ним. За исключением
редких патологических случаев, время, необходимое для хранения элемента или доступа
к нему, не зависит от количества элементов, которые находятся в ассоциативном массиве.
Высокая производительность хэш-таблиц достигается за счет хранения
элементов неупорядоченным образом. Кроме того, в отличие от массивов, элементы хэш-таблиц
не хранятся один за одним.
Для простых массивов значения индексов вообще не сохраняются. Поскольку элементы массива являются
хранящиеся бок о бок в памяти значения индексов неявно представляют собой относительные позиции
элементов с начала массива.
С другой стороны, ассоциативные массивы действительно хранят как ключи, так и значения
элементов. Хотя это различие заставляет ассоциативные массивы использовать больше памяти, оно
также позволяет им использовать разреженные значения ключей. Например, когда
для ключей 0 и 999 требуется сохранить только два элемента, ассоциативный массив хранит только два элемента,
а не 1000, как это должно быть в обычном массиве.

Определение ассоциативного массива
-----------------------------------


Синтаксис ассоциативных массивов аналогичен синтаксису массива. Разница
в том, что в квадратных скобках указывается тип ключа, а не
длина массива. Например ассоциативный массив отображающий название дня (тип string) на его номер (тип int) может быть определен вот так

.. code-block:: d

    int[string] dayNumbers;

Переменная dayNumbers представляет собой ассоциативный массив, который можно использовать в качестве таблицы,
обеспечивающей сопоставление названий дней с номерами дней. Другими словами, она может
использоваться как противоположность массиву DayNames в начале этой главы.
В примерах ниже мы будем использовать ассоциативный массив dayNumbers.
Ключи ассоциативных массивов могут быть любого типа, включая определяемые пользователем
типы структур и классов. Мы познакомимся с пользовательскими типами в последующих главах.
Длина ассоциативных массивов не может быть указана при определении. Они увеличиваются
автоматически по мере добавления пар ключ-значение.
*Примечание: Ассоциативный массив, определенный без какого-либо элемента, равен null (стр. 233),
а не пуст. Это различие имеет важное значение при передаче ассоциативных
преобразование массивов в функции (стр. 168). Мы рассмотрим эти концепции в последующих главах.*


Добавление пары ключ-значение
------------------------------

Оператор присваивания может быть использован для создания ассоциации между ключом и значением.

.. code-block:: d

    //  пара ключ - значение ключ = 0, значение = "Monday"
    dayNumbers["Monday"] = 0;
    //  - значение ключ = 1, значение = "Tuesday"
    dayNumbers["Tuesday"] = 1;

Таблица автоматически увеличивается с добавлением новый пары ключ-значение. Например, номера дней
будут иметь две пары ключ-значение после описанных выше операций. Это можно
продемонстрировать, распечатав всю таблицу целиком:

.. code-block:: d

    writeln(dayNumbers);

Если распечать весь массив, то мы увидим, что значения 0 и 1 соответствуют ключам "Monday" и
"Tuesday" соответственно:

.. code-block:: console

    ["Monday":0, "Tuesday":1]

Для каждого ключа может быть только одно значение. По этой причине, когда мы назначаем новую  пару ключ-значение, а ключ уже существует,
таблица не увеличивается; вместо этого изменяется значение существующего ключа:

.. code-block:: d

    dayNumbers["Tuesday"] = 222;
    writeln(dayNumbers);

Вывод

.. code-block:: console

    ["Monday":0, "Tuesday":222]

Инициализация ассоциативного массива
------------------------------------

Иногда некоторые пары ключа - значения уже известны на момент определения ассоциативного массива.
Ассоциативные массивы инициализируются аналогично обычным массивам, используя двоеточие для отделения каждого ключа от
соответствующего ему значения:

.. code-block:: d

    int[string] dayNumbers = [ "Monday" : 0, "Tuesday" : 1, "Wednesday" : 2,
                               "Thursday" : 3, "Friday" : 4, "Saturday" : 5,
                               "Sunday" : 6 ];
    writeln(dayNumbers["Tuesday"]); // prints 1

Удаление пары ключ-значение
---------------------------

Пара ключ-значение может быть удалена при помощи свойства .remove()

.. code-block:: d

    dayNumbers.remove("Tuesday");
    writeln(dayNumbers["Tuesday"]); // ← ошибка времени исполнения

Первая строка выше удаляет пару ключ-значение "Tuesday" / 1. Поскольку этого ключа больше нет
в контейнере, вторая строка приведет к возникновению исключения
и завершению работы программы, если это исключение не будет перехвачено. Мы рассмотрим
исключения в следующей главе (стр. 192). Свойство .clear удаляет все элементы:

.. code-block:: d

    dayNumbers.clear; // ассоциативный массив пуст


Проверка наличия ключа
-----------------------

Оператор in определяет, существует ли данный ключ в ассоциативном массиве:

.. code-block:: d

    int[string] colorCodes = [ /* ... */ ];
    if ("purple" in colorCodes) {
    // ключ "purple" присутствует в таблице
    } else {
    // ключ "purple" не найдени в таблице
    }

Иногда имеет смысл использовать значение по умолчанию, если ключ не существует в
ассоциативном массиве. Например, специальное значение -1 может использоваться в качестве кода для
цветов, которых нет в цветовых кодах. .get() полезен в таких случаях: он возвращает
значение, связанное с указанным ключом, если этот ключ существует, в противном случае он возвращает значение по
умолчанию. Значение по умолчанию задается в качестве второго параметра .get():

.. code-block:: d

    int[string] colorCodes = [ "blue" : 10, "green" : 20 ];
    writeln(colorCodes.get("purple", -1));

Так как ключа "purple" нет в массиве,то get вернёт -1

.. code-block:: console

    -1

Свойства
--------

.. index::
    .length
    .keys
    .byKey
    .byKey
    .values
    .byValue
    .byKeyValue
    .rehash
    .sizeof
    .get
    .remove
    .clear




* .length возвращает количество пар ключ-значение.
* .keys возвращает копию всех ключей в виде динамического массива.
* .byKey обеспечивает доступ к ключам без их копирования; мы увидим, как
  .byKey используется в циклах foreach в следующей главе.
* .values возвращает копию всех значений в виде динамического массива.
* .byValue предоставляет доступ к значениям без их копирования.
* .byKeyValue предоставляет доступ к парам ключ-значение без их копирования.
* .rehash может сделать массив более эффективным в некоторых случаях, например, после
   вставки большого количества пар ключ-значение.
* .sizeof - это размер ссылки на массив (он не имеет ничего общего с количеством
   пар ключ-значение в таблице и является одинаковым значением для всех ассоциативных массивов).
* .get возвращает значение, если оно существует, в противном случае значение по умолчанию.
* .remove удаляет указанный ключ и его значение из массива.
* .clear удаляет все элементы.


Пример
------

Вот программа, которая печатает турецкие названия цветов, которые указаны на
английском языке:

.. code-block:: d

    import std.stdio;
    import std.string;

    void main()
    {
        string[string] colors = [
            "black": "siyah",
            "white": "beyaz",
            "red": "kırmızı",
            "green": "yeşil",
            "blue": "mavi"
        ];
        writefln("I know the Turkish names of these %s colors: %s",
            colors.length, colors.keys);
        write("Please ask me one: ");
        string inEnglish = strip(readln());
        if (inEnglish in colors)
        {
            writefln("\"%s\" is \"%s\" in Turkish.", inEnglish, colors[inEnglish]);
        }
        else
        {
            writeln("I don't know that one.");
        }
    }


Упражнение
----------

#. Как можно удалить все пары ключ-значение ассоциативного массива,
   кроме вызова .clear? (.clear - наиболее естественный метод.) Существует как минимум
   три метода:

   * Удаление их по очереди из ассоциативного массива.
   * Присвоение пустого ассоциативного массива.
   * Аналогично предыдущему методу, присваиваем свойству .init массива.

*Примечание: Свойство .init любой переменной или типа является начальным значением этого
типа:*

.. code-block:: d

    number = int.init; // 0 для типа int

#. Как и в случае с массивами, для каждого ключа может быть только одно значение. Это может
   рассматриваться как ограничение для некоторых приложений.
   Предположим, что ассоциативный массив используется для хранения оценок учащихся.
   Например, давайте предположим, что оценки 90, 85, 95 и т.д. должны быть сохранены для
   ученика с именем "эмре".
   Ассоциативные массивы упрощают доступ к оценкам по имени
   учащегося, как в grades["emre"]. Однако оценки не могут быть вставлены, как в
   следующем коде, поскольку каждая оценка перезаписывает предыдущую:

.. code-block:: d

    int[string] grades;
    grades["emre"] = 90;
    grades["emre"] = 85; // ← предыдущее значение будет перезаписано

Как вы можете решить эту проблему? Определите ассоциативный массив, который может хранить
несколько оценок для каждого учащегося.

